package codeTop;

import java.util.ArrayList;
import java.util.List;

public class q93 {
    public List<String> restoreIpAddresses(String s) {
        if (s.length() > 12 || s.length() < 4) {
            return new ArrayList<>();
        }
        dfs(s,s.length(),4,0,new ArrayList<>());
        return res;
    }
    List<String> res = new ArrayList<>();
    void dfs(String s,int remainLength,int remainBlocks,int idx,List<String> list){
        if (remainBlocks == 0 && remainLength == 0) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < 3; i++) {
                sb.append(list.get(i));
                sb.append('.');
            }
            sb.append(list.get(3));
            res.add(sb.toString());
        }
        if (remainLength == 0 || remainBlocks == 0) {
            return;
        }
        //取一位
        if (idx < s.length()) {
            if (remainLength - 1 <= (remainBlocks - 1) * 3) {
                list.add(s.substring(idx,idx+1));
                dfs(s,remainLength-1,remainBlocks-1,idx+1,list);
                list.remove(list.size()-1);
            }
            if (s.charAt(idx) == '0') {
                return;
            }
        }else {
            return;
        }
        //取两位
        if (idx < s.length() - 1) {
            if (remainLength - 2 <= (remainBlocks - 1) * 3) {
                list.add(s.substring(idx,idx+2));
                dfs(s,remainLength-2,remainBlocks-1,idx+2,list);
                list.remove(list.size()-1);
            }
        }else {
            return;
        }
        //取三位
        if (idx < s.length() - 2) {
            String s1 = s.substring(idx, idx + 3);
            int i = Integer.parseInt(s1);
            if (remainLength - 3 <= (remainBlocks - 1) * 3&&i>=100&&i<=255) {
                list.add(s1);
                dfs(s,remainLength-3,remainBlocks-1,idx+3,list);
                list.remove(list.size()-1);
            }
        }
    }

    public static void main(String[] args) {
        q93 q = new q93();
        System.out.println(q.restoreIpAddresses("101023"));
    }
}
